//对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。 
//
// 给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "ab", s2 = "ba"
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：s1 = "abc", s2 = "bca"
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length <= 20 
// s2.length == s1.length 
// s1 和 s2 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母 
// s2 是 s1 的一个字母异位词 
// 
// Related Topics广度优先搜索 | 字符串 
//
// 👍 156, 👎 0 
//
//
//
//

package leetcode.editor.day;

import java.util.*;

// 854. 相似度为 K 的字符串
// https://leetcode.cn/problems/k-similar-strings/
class KSimilarStrings {
    public static void main(String[] args) {
        Solution solution = new KSimilarStrings().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // https://leetcode.cn/problems/k-similar-strings/solution/-by-lcbin-snnw/
        // BFS来搜索
        public int kSimilarity(String s1, String s2) {
            Queue<String> queue = new LinkedList<>();
            Set<String> set = new HashSet<>();
            queue.offer(s1);
            set.add(s1);
            int step = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String str = queue.poll();
                    // 相等直接返回，BFS此时肯定是交换次数最小的
                    if (str.equals(s2)) {
                        return step;
                    }

                    for (String next : nextStr(str, s2)) {
                        // 剪枝，不包含就跳过
                        if (!set.contains(next)) {
                            queue.offer(next);
                            set.add(next);
                        }
                    }
                }
                // 每一层步数加一
                step++;
            }

            return step;
        }

        // 此时s1[i] != s2[i]，所以需要在s1的i开始找到一个j，s1[j] == s2[i]，与其s1[i]交换，由于可能重复，所以需要集合
        public List<String> nextStr(String s1, String s2) {
            int i = 0;
            // 从不相等开始
            char[] arr1 = s1.toCharArray(), arr2 = s2.toCharArray();
            while (i < arr1.length && arr1[i] == arr2[i]) i++;

            List<String> res = new ArrayList<>();
            for (int j = i + 1; j < arr1.length; j++) {
                if (arr1[j] == arr2[i] && arr1[j] != arr1[i]) {
                    swap(arr1, i, j);
                    res.add(new String(arr1));
                    // 恢复继续搜索
                    swap(arr1, i, j);
                }
            }

            return res;
        }

        public void swap(char[] arr, int i, int j) {
            char c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
